﻿#define _CRT_SECURE_NO_WARNINGS 1
//题目：有边数限制的最短路（bellman_ford算法）
//给定一个 n个点 m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
//请你求出从 1号点到 n号点的最多经过 k条边的最短距离，如果无法从 1号点走到 n号点，输出 impossible。
//注意：图中可能 存在负权回路 。
//输入格式第一行包含三个整数 n, m, k。
//接下来 m行，每行包含三个整数 x, y, z，表示存在一条从点 x到点 y的有向边，边长为 z。
//点的编号为 1∼n。
//输出格式
//输出一个整数，表示从 1号点到 n号点的最多经过 k条边的最短距离。
//如果不存在满足条件的路径，则输出 impossible。
//数据范围
//1≤n, k≤500,1≤m≤10000,1≤x, y≤n，任意边长的绝对值不超过 10000。
//输入样例：
//3 3 1
//1 2 1
//2 3 1
//1 3 3
//输出样例：
//3
//#include<iostream>
//#include<cstring>
//
//using namespace std;
//
//const int N = 510, M = 10010;
//
//struct Edge { //使用结构体存储边，不用定义一大堆数组去加边
//    int a;
//    int b;
//    int w;
//} e[M];//把每个边保存下来即可
//int dist[N];
//int back[N];//备份数组防止串联
//int n, m, k;//k代表最短路径最多包涵k条边
//
//void bellman_ford() {
//    memset(dist, 0x3f, sizeof dist); //dist初始化位无穷，八字节3f3f3f3f大于1e9
//    dist[1] = 0;
//    for (int i = 0; i < k; i++) {//k次循环
//        memcpy(back, dist, sizeof dist);//
//        for (int j = 0; j < m; j++) {//遍历所有边，而dijkstra是遍历所有顶点n*n
//            int a = e[j].a, b = e[j].b, w = e[j].w;
//            dist[b] = min(dist[b], back[a] + w);
//            //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
//        }
//    }
//}
//
//int main() {
//    scanf("%d%d%d", &n, &m, &k);
//    for (int i = 0; i < m; i++) {
//        int a, b, w;
//        scanf("%d%d%d", &a, &b, &w);
//        e[i] = { a, b, w };
//    }
//    bellman_ford();
//    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
//    else printf("%d", dist[n]);
//    return 0;
//}

//题目：spfa求最短路
//给定一个 n个点 m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
//请你求出 1号点到 n号点的最短距离，如果无法从 1号点走到 n号点，则输出 impossible。
//数据保证不存在负权回路。
//输入格式
//第一行包含整数 n和 m。
//接下来 m行每行包含三个整数 x, y, z，表示存在一条从点 x到点 y的有向边，边长为 z。
//输出格式
//输出一个整数，表示 1号点到 n号点的最短距离。
//如果路径不存在，则输出 impossible。
//数据范围
//1≤n, m≤105,图中涉及边长绝对值均不超过 10000。
//输入样例：
//3 3
//1 2 5
//2 3 - 3
//1 3 4
//输出样例：
//2
//#include <iostream>
//#include <algorithm>
//#include <cstring>
//using namespace std;
//
//const int N = 100010;
//int h[N], e[N], w[N], ne[N], idx;//邻接表，存储图
//int st[N];//标记顶点是不是在队列中
//int dist[N];//保存最短路径的值
//int q[N], hh, tt = -1;//队列
//
//void add(int a, int b, int c) {//图中添加边和边的端点
//    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
//}
//
//void spfa() {
//    q[++tt] = 1;//从1号顶点开始松弛，1号顶点入队
//    dist[1] = 0;//1号到1号的距离为 0
//    st[1] = 1;//1号顶点在队列中
//    while (tt >= hh) {//不断进行松弛
//        int a = q[hh++];//取对头记作a，进行松弛
//        st[a] = 0;//取完队头后，a不在队列中了
//        for (int i = h[a]; i != -1; i = ne[i])//遍历所有和a相连的点
//        {
//            int b = e[i], c = w[i];//获得和a相连的点和边
//            if (dist[b] > dist[a] + c) {//如果可以距离变得更短，则更新距离
//
//                dist[b] = dist[a] + c;//更新距离
//
//                if (!st[b]) {//如果没在队列中
//                    q[++tt] = b;//入队
//                    st[b] = 1;//打标记
//                }
//            }
//        }
//    }
//}
//int main() {
//    memset(h, -1, sizeof h);//初始化邻接表
//    memset(dist, 0x3f, sizeof dist);//初始化距离
//    int n, m;//保存点的数量和边的数量
//    cin >> n >> m;
//    for (int i = 0; i < m; i++) {//读入每条边和边的端点
//        int a, b, w;
//        cin >> a >> b >> w;
//        add(a, b, w);//加入到邻接表
//    }
//    spfa();
//    if (dist[n] == 0x3f3f3f3f)//如果到n点的距离是无穷，则不能到达 
//        cout << "impossible";
//    else cout << dist[n];//否则能到达，输出距离
//    return 0;
//}

